// Author: Hongliang Gao;   Created: Jan 27 2011
// Description: sample predictors for cbp3.

#include <stdio.h>
#include <cassert>
#include <map>
#include <string.h>
#include <inttypes.h>
#include <sstream>
#include <list>

using namespace std;
#include "cbp3_def.h"
#include "cbp3_framework.h"

// this file includes two sample predictors
// one is a 64 KB gshare conditional predictor
// the other is a 64 KB indirect predictor indexed by (pc ^ history)

// rewind_marked is also used to show how to rewind the reader for multiple runs
// the predictor will use gshare in the first run
// the indirect predictor will be used in the second run

// NOTE: rewind_marked is only provided to help tuning work. the final
// submitted code should only include one run.

#ifdef LARGE
#define GSHARE_SIZE 24
#elif defined LARGER
#define GSHARE_SIZE 72
#else
#define GSHARE_SIZE 18 // 256K 2-bit counters = 64 KB cost
#endif
#define IND_SIZE 14    // 16K 32-bit targets  = 64 KB cost

#ifndef INIT_VALUE
#define INIT_VALUE 0
#endif

struct my_int {
  int value;
  my_int(): value(INIT_VALUE) {}
};

#ifdef INF_SIZE 
map<uint32_t , my_int> gtable;
map<uint32_t , my_int> correlation;
#elif defined NO_COLLISIONS
map<pair<uint32_t,uint32_t>, my_int> gtable;
map<pair<uint32_t,uint32_t>, uint32_t> correlation;
uint32_t correlation_counter;
#elif defined PATH_HISTORY
list<uint32_t> fetch_path;
list<uint32_t> retire_path;

map<string , my_int> gtable;
map<string , uint32_t> correlation;
uint32_t correlation_counter;
#elif defined BASELINE
int8_t *gtable;
#elif defined GSHARE_ONE
bool *gtable;
#endif
uint32_t *indtable;

// cost: depending on predictor size
uint32_t brh_fetch;
uint32_t brh_retire;

// count number of runs
//uint32_t runs;

void PredictorInit() {
    //runs = 0;

#ifdef INF_SIZE
  gtable.clear();
#elif defined NO_COLLISIONS
  gtable.clear();
#elif defined PATH_HISTORY
  gtable.clear();
  for (int i=0;i<32;i++) {
    fetch_path.push_back(0); 
    retire_path.push_back(0);
  }
#elif defined BASELINE
    gtable = new int8_t[1 << GSHARE_SIZE];
#elif defined GSHARE_ONE
    gtable = new bool[1 << GSHARE_SIZE];
#endif
    indtable = new uint32_t[1 << IND_SIZE];
}

void PredictorReset() {
    
#ifdef INF_SIZE
  gtable.clear();
#elif defined NO_COLLISIONS
  gtable.clear();
  correlation.clear();
  correlation_counter = 0;
#elif defined PATH_HISTORY
  gtable.clear();
  fetch_path.clear();
  retire_path.clear();
  for (int i=0;i<32;i++) {
     fetch_path.push_back(0);
     retire_path.push_back(0);
  }
  correlation.clear();
  correlation_counter = 0;

#elif defined BASELINE
  for (int i = 0; i < (1 << GSHARE_SIZE); i ++)
      gtable[i] = INIT_VALUE;
#elif defined GSHARE_ONE
  for (int i = 0; i < (1 << GSHARE_SIZE); i ++)
      gtable[i] = true;
#endif
  
for (int i = 0; i < (1 << IND_SIZE); i ++)
    indtable[i] = 0;

    brh_fetch = 0;
    brh_retire = 0;
  
}

#ifdef PATH_HISTORY
string gen_fetch_index(uint32_t pc) {
  stringstream out;
  list<uint32_t>::iterator it;
  for (it=fetch_path.begin(); it!=fetch_path.end(); ++it) {
    out << *it;
    out << "&";
  }
  out << brh_fetch;
  out << "&";
  out << pc;
  return out.str();
}
string gen_retire_index(uint32_t pc) {
  stringstream out;
  list<uint32_t>::iterator it;
  for (it=retire_path.begin(); it!=retire_path.end(); ++it) {
    out << *it;
    out << "&";
  }
  out << brh_retire;
  out << "&";
  out << pc;
  return out.str();
}
#endif


uint32_t get_correlation(uint32_t pc){
 #ifdef INF_SIZE
  return (brh_fetch ^ pc); // correlation is index
#elif defined NO_COLLISIONS
  pair<uint32_t,uint32_t> key(brh_fetch,pc);
  if( correlation[key] == 0 ){
    ++correlation_counter;
    correlation[key] = correlation_counter;
  }
  return correlation[key];
#elif defined PATH_HISTORY
  string key = gen_fetch_index(pc);
  if( correlation[key] == 0 ){
    ++correlation_counter;
    correlation[key] = correlation_counter;
  }
  return correlation[key];
#elif defined BASELINE
  uint32_t gidx = (brh_fetch ^ pc) & ((1 << GSHARE_SIZE) - 1);
  return gidx; // correlation is index
#elif defined GSHARE_ONE
  uint32_t gidx = (brh_fetch ^ pc) & ((1 << GSHARE_SIZE) - 1);
  return gidx; // correlation is index
#endif 
}


bool get_prediction(uint32_t pc) {
#ifdef INF_SIZE
  return (gtable[(brh_fetch ^ pc)].value >= 0);
#elif defined NO_COLLISIONS
  pair<uint32_t,uint32_t> key(brh_fetch,pc);
  return (gtable[key].value >= 0);
#elif defined PATH_HISTORY
  return (gtable[gen_fetch_index(pc)].value >= 0);
#elif defined BASELINE
  uint32_t gidx = (brh_fetch ^ pc) & ((1 << GSHARE_SIZE) - 1);
  return (gtable[gidx] >= 0);
#elif defined GSHARE_ONE
  uint32_t gidx = (brh_fetch ^ pc) & ((1 << GSHARE_SIZE) - 1);
  return (gtable[gidx]);
#endif

}

void update(uint32_t pc , bool br_outcome) {
#ifdef CHEAT
  
#ifdef INF_SIZE
  uint32_t gidx = brh_fetch ^ pc;
  if (br_outcome && gtable[gidx].value < 1)
       gtable[gidx].value++;
  else if (!br_outcome && gtable[gidx].value > -2)
       gtable[gidx].value--;  
#elif defined NO_COLLISIONS
  pair<uint32_t,uint32_t> gidx(brh_fetch,pc);
  if (br_outcome && gtable[gidx].value < 1)
       gtable[gidx].value ++;
  else if (!br_outcome && gtable[gidx].value > -2)
       gtable[gidx].value --;
#elif defined PATH_HISTORY
  string gidx = gen_fetch_index(pc);
  if (br_outcome && gtable[gidx].value < 1)
       gtable[gidx].value ++;
  else if (!br_outcome && gtable[gidx].value > -2)
       gtable[gidx].value --;
#elif defined GSHARE_ONE
  uint32_t gidx = (brh_fetch ^ pc) & ((1 << GSHARE_SIZE) - 1);
  gtable[gidx] = br_outcome;
#elif defined BASELINE
  uint32_t gidx = (brh_fetch ^ pc) & ((1 << GSHARE_SIZE) - 1);
    if (br_outcome && gtable[gidx] < 1)
       gtable[gidx] ++;
    else if (!br_outcome && gtable[gidx] > -2)
       gtable[gidx] --;
#endif

#else

#ifdef INF_SIZE
  uint32_t gidx = brh_retire ^ pc;
  if (br_outcome && gtable[gidx].value < 1)
       gtable[gidx].value++;
  else if (!br_outcome && gtable[gidx].value > -2)
       gtable[gidx].value--;  
#elif defined NO_COLLISIONS
  pair<uint32_t,uint32_t> gidx(brh_retire,pc);
  if (br_outcome && gtable[gidx].value < 1)
       gtable[gidx].value ++;
  else if (!br_outcome && gtable[gidx].value > -2)
       gtable[gidx].value --;
#elif defined PATH_HISTORY
  string gidx = gen_retire_index(pc);
  if (br_outcome && gtable[gidx].value < 1)
       gtable[gidx].value ++;
  else if (!br_outcome && gtable[gidx].value > -2)
       gtable[gidx].value --;
#elif defined GSHARE_ONE
  uint32_t gidx = (brh_retire ^ pc) & ((1 << GSHARE_SIZE) - 1);
  gtable[gidx] = br_outcome;
#elif defined BASELINE
  uint32_t gidx = (brh_retire ^ pc) & ((1 << GSHARE_SIZE) - 1);
    if (br_outcome && gtable[gidx] < 1)
       gtable[gidx] ++;
    else if (!br_outcome && gtable[gidx] > -2)
       gtable[gidx] --;
#endif


#endif

}

void PredictorRunACycle() {
    // get info about what uops are processed at each pipeline stage
    const cbp3_cycle_activity_t *cycle_info = get_cycle_info();

    // make prediction at fetch stage
    for (int i = 0; i < cycle_info->num_fetch; i++) {
        uint32_t fe_ptr = cycle_info->fetch_q[i];
        const cbp3_uop_dynamic_t *uop = &fetch_entry(fe_ptr)->uop;

        if (/* runs == 0 && */uop->type & IS_BR_CONDITIONAL) {
     
	  assert(report_pred(fe_ptr, false, get_prediction(uop->pc),get_correlation(uop->pc)));
	#ifdef CHEAT
	  update(uop->pc,uop->br_taken);
        #endif
        }else if (/* runs == 1 && */ uop->type & IS_BR_INDIRECT) {
  
	}

        // update fetch branch history
        if (uop->type & IS_BR_CONDITIONAL)
            brh_fetch = (brh_fetch << 1) | (uop->br_taken ? 1 : 0);
        else if (uop_is_branch(uop->type))
            brh_fetch = (brh_fetch << 1) | 1;
        #ifdef PATH_HISTORY
	    fetch_path.pop_back();
            fetch_path.push_front(uop->br_target);
	#endif

	
    }

    for (int i = 0; i < cycle_info->num_retire; i++) {
        uint32_t rob_ptr = cycle_info->retire_q[i];
        const cbp3_uop_dynamic_t *uop = &rob_entry(rob_ptr)->uop;

        if (/*runs == 0 &&*/ uop->type & IS_BR_CONDITIONAL) {
        #ifndef CHEAT
	  update(uop->pc,uop->br_taken);
        #endif
	}else if (/*runs == 1 &&*/ uop->type & IS_BR_INDIRECT) {
        }

        // update retire branch history
        if (uop->type & IS_BR_CONDITIONAL)
            brh_retire = (brh_retire << 1) | (uop->br_taken ? 1 : 0);
        else if (uop_is_branch(uop->type))
            brh_retire = (brh_retire << 1) | 1;
        
        #ifdef PATH_HISTORY
	    retire_path.pop_back();
            retire_path.push_front(uop->br_target);
	#endif


    }
}

void PredictorRunEnd() {
/*
    runs ++;
    if (runs < 2) // set rewind_marked to indicate that we want more runs
        rewind_marked = true;
*/
}

void PredictorExit() {
}
